//
// Description: 671. 二叉树中第二小的节点
// Created by Loading on 2021/7/27.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

int findSecondMinimumValue(TreeNode *root) {
    // 整棵树的最小值为 根节点的值
    int min_value = root->val;
    int res = -1;

    function<void(TreeNode *)> dfs = [&](TreeNode *node) {
        if (!node) {
            return;
        }
        /* 剪枝 */
        // 已找到备选的第二小的值且当前节点的值 >= 备选值，无需继续向后递归
        if (res != -1 && node->val >= res) {
            return;
        }
        // 找到备选第二小的值
        if (node->val > min_value) {
            res = node->val;
        }
        dfs(node->left);
        dfs(node->right);
    };
    dfs(root);

    return res;
}

int main() {
    auto *root = new TreeNode(2);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);

    cout << findSecondMinimumValue(root) << endl;
}